<!DOCTYPE html>
<html>
<!--
Copyright 2007 The Closure Library Authors. All Rights Reserved.

Use of this source code is governed by an Apache 2.0 License.
See the COPYING file for details.
-->
<head>
<title>Closure Unit Tests - goog.structs.AvlTree</title>
<script src="../base.js"></script>
<script>
  goog.require('goog.structs');
  goog.require('goog.structs.AvlTree');
  goog.require('goog.testing.jsunit');
</script>
</head>
<body>
<script>

  /**
   * This test verifies that we can insert strings into the AvlTree and have 
   * them be stored and sorted correctly by the default comparator.
   */
  function testInsertsWithDefaultComparator() {
    var tree = new goog.structs.AvlTree();
    var values = ['bill', 'blake', 'elliot', 'jacob', 'john', 'myles', 'ted'];
    
    // Insert strings into tree out of order
    tree.add(values[4]);
    tree.add(values[3]);
    tree.add(values[0]);
    tree.add(values[6]);
    tree.add(values[5]);
    tree.add(values[1]);
    tree.add(values[2]);
    
    // Verify strings are stored in sorted order
    var i = 0;
    tree.inOrderTraverse(function(value) {
      assertEquals(values[i], value);
      i += 1;
    });
    assertEquals(i, values.length);
  };

  /**
   * This test verifies that we can insert strings into and remove strings from
   * the AvlTree and have the only the non-removed values be stored and sorted 
   * correctly by the default comparator.
   */
  function testRemovesWithDefaultComparator() {
    var tree = new goog.structs.AvlTree();
    var values = ['bill', 'blake', 'elliot', 'jacob', 'john', 'myles', 'ted'];
    
    // Insert strings into tree out of order
    tree.add('frodo');
    tree.add(values[4]);
    tree.add(values[3]);
    tree.add(values[0]);
    tree.add(values[6]);
    tree.add('samwise');        
    tree.add(values[5]);
    tree.add(values[1]);
    tree.add(values[2]);
    tree.add('pippin');
    
    // Remove strings from tree
    assertEquals(tree.remove('samwise'), 'samwise');
    assertEquals(tree.remove('pippin'), 'pippin');
    assertEquals(tree.remove('frodo'), 'frodo');
    assertEquals(tree.remove('merry'), null);
    
    
    // Verify strings are stored in sorted order
    var i = 0;
    tree.inOrderTraverse(function(value) {
      assertEquals(values[i], value);
      i += 1;
    });
    assertEquals(i, values.length);
  };

  /**
   * This test verifies that we can insert values into and remove values from 
   * the AvlTree and have them be stored and sorted correctly by a custom 
   * comparator.
   */
  function testInsertsAndRemovesWithCustomComparator() {
    var tree = new goog.structs.AvlTree(function(a, b) {
      return a - b;
    });
        
    var NUM_TO_INSERT = 37;
    var valuesToRemove = [1, 0, 6, 7, 36];
        
    // Insert ints into tree out of order
    var values = [];
    for (var i = 0; i < NUM_TO_INSERT; i += 1) {
      tree.add(i);
      values.push(i);
    }    
    
    for (var i = 0; i < valuesToRemove.length; i += 1) {
      assertEquals(tree.remove(valuesToRemove[i]), valuesToRemove[i]); 
      goog.array.remove(values, valuesToRemove[i]);
    }
    assertEquals(tree.remove(-1), null);
    assertEquals(tree.remove(37), null);
    
    // Verify strings are stored in sorted order
    var i = 0;
    tree.inOrderTraverse(function(value) {
      assertEquals(values[i], value);
      i += 1;
    });
    assertEquals(i, values.length);    
  };
  
  /**
   * This test verifies that we can insert values into and remove values from 
   * the AvlTree and have it maintain the AVL-Tree upperbound on its height.
   */
  function testAvlTreeHeight() {
    var tree = new goog.structs.AvlTree(function(a, b) {
      return a - b;
    });
        
    var NUM_TO_INSERT = 2000;
    var NUM_TO_REMOVE = 500;
        
    // Insert ints into tree out of order
    for (var i = 0; i < NUM_TO_INSERT; i += 1) {
      tree.add(i);
    }    
    
    // Remove valuse
    for (var i = 0; i < NUM_TO_REMOVE; i += 1) {
      tree.remove(i);
    }    
    
    assertTrue(tree.getHeight() <= 1.4405 * 
        (Math.log(NUM_TO_INSERT - NUM_TO_REMOVE + 2) / Math.log(2)) - 1.3277);    
  };  

  /**
   * This test verifies that we can insert values into and remove values from 
   * the AvlTree and have its contains method correctly determine the values it
   * is contains.
   */
  function testAvlTreeContains() {
    var tree = new goog.structs.AvlTree();    
    var values = ['bill', 'blake', 'elliot', 'jacob', 'john', 'myles', 'ted'];
    
    // Insert strings into tree out of order
    tree.add('frodo');
    tree.add(values[4]);
    tree.add(values[3]);
    tree.add(values[0]);
    tree.add(values[6]);
    tree.add('samwise');        
    tree.add(values[5]);
    tree.add(values[1]);
    tree.add(values[2]);
    tree.add('pippin');
    
    // Remove strings from tree
    assertEquals(tree.remove('samwise'), 'samwise');
    assertEquals(tree.remove('pippin'), 'pippin');
    assertEquals(tree.remove('frodo'), 'frodo');    
    
    for (var i = 0; i < values.length; i += 1) {
      assertTrue(tree.contains(values[i]));
    }
    assertFalse(tree.contains('samwise'));
    assertFalse(tree.contains('pippin'));
    assertFalse(tree.contains('frodo'));    
  };  
  
  /**
   * This test verifies that we can insert values into and remove values from 
   * the AvlTree and have its minValue and maxValue routines return the correct
   * min and max values contained by the tree.
   */
  function testMinAndMaxValues() {
    var tree = new goog.structs.AvlTree(function(a, b) {
      return a - b;
    });
        
    var NUM_TO_INSERT = 2000;
    var NUM_TO_REMOVE = 500;
        
    // Insert ints into tree out of order
    for (var i = 0; i < NUM_TO_INSERT; i += 1) {
      tree.add(i);
    }    
    
    // Remove valuse
    for (var i = 0; i < NUM_TO_REMOVE; i += 1) {
      tree.remove(i);
    }    
    
    assertEquals(tree.getMinimum(), NUM_TO_REMOVE);   
    assertEquals(tree.getMaximum(), NUM_TO_INSERT - 1);   
  };  

  /**
   * This test verifies that we can insert values into and remove values from 
   * the AvlTree and traverse the tree in reverse order using the 
   * reverseOrderTraverse routine.
   */
  function testReverseOrderTraverse() {
    var tree = new goog.structs.AvlTree(function(a, b) {
      return a - b;
    });
        
    var NUM_TO_INSERT = 2000;
    var NUM_TO_REMOVE = 500;
        
    // Insert ints into tree out of order
    for (var i = 0; i < NUM_TO_INSERT; i += 1) {
      tree.add(i);
    }    
    
    // Remove valuse
    for (var i = 0; i < NUM_TO_REMOVE; i += 1) {
      tree.remove(i);
    }    
    
    var i = NUM_TO_INSERT - 1;
    tree.reverseOrderTraverse(function(value) {
      assertEquals(value, i);
      i -= 1;
    });    
    assertEquals(i, NUM_TO_REMOVE - 1);
  };  

</script>
</body>
</html>
